package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.stream.Stream;

/**
 * 1104. 二叉树寻路
 * @author feizns
 * @since 2020/3/17
 */
public class PathInZigZagTree {

    static class P {
        String getId(){return null;}
    }

    public static void main(String[] args) {
        List<P> ps = Arrays.asList(new P());
//        System.out.println(pathInZigZagTree(26));
    }

    public static List<Integer> pathInZigZagTree(int label) {
        int i = helper(1, 1, label);
        return ans;
    }

    static LinkedList<Integer> ans = new LinkedList<>();

    private static int helper(int min, int level, int label) {
        int max = (int) Math.pow(2, level) - 1;
        int dif;
        if ( label <= max ) {
            if ( level % 2 == 0 )
                dif = max - label;
            else
                dif = label - min;
        } else {
            int prev = helper(max + 1, level + 1, label);
            int curt = prev / 2;
            dif = curt - min;
        }
        if ( level % 2 == 0 )
            ans.addFirst(max - dif);
        else
            ans.addFirst(min + dif);
        return min + dif;
    }

}
